﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace AnaxibiaStudios.BeanPermutator.Brute
{
  public class Permutator<T> : PermuteBase<T>
  {
    private List<List<T>> _result;
    private int _iterationIndex;

    public override IEnumerable<T> Current
    {
      get { return _result[_iterationIndex]; }
    }

    public Permutator(IList<T> source, Func<T, T, bool> canSwap)
      : base(source, canSwap)
    {
      Reset();
    }

    public override void Dispose() { }

    public override bool MoveNext()
    {
      if (_iterationIndex == -1)
        BuildAllPerms();
      else if (_iterationIndex >= _result.Count)
        return false;

      while (true)
      {
        _iterationIndex++;

        if (_iterationIndex >= _result.Count)
          return false;

        if (ValidPerm())
          return true;
      }
    }

    private bool ValidPerm()
    {
      var current = Current as List<T>;

      for (int i = 0; i < current.Count - 1; i++)
      {
        for (int j = i + 1; j < current.Count; j++)
        {
          if (!CanSwap(current[j], current[i]))
          {
            return false;
          }
        }
      }

      return true;
    }

    private void BuildAllPerms()
    {
      Permute(new List<T>(), _source);
    }

    private void Permute(List<T> prefix, IList<T> sub)
    {
      if (sub.Count <= 1)
      {
        var perm = new List<T>(prefix);
        perm.AddRange(sub);
        _result.Add(perm);
      }
      else
      {
        for (int i = 0; i < sub.Count; i++)
        {
          var pop = sub[i];
          sub.RemoveAt(i);

          prefix.Add(pop);
          Permute(prefix, sub);
          prefix.RemoveAt(prefix.Count - 1);

          sub.Insert(i, pop);
        }
      }
    }

    public override void Reset()
    {
      _result = new List<List<T>>();
      _iterationIndex = -1;
    }
  }
}
